package com;


import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @authoer zsj
 * @date 2022/5/30 17:29
 * <p>
 * 每日一题
 */
public class EDayExam {


    private TreeNode root;
    private TreeNode subRoot;

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 给出一棵二叉树，其上每个结点的值都是0或1。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
     * 例如，如果路径为0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数01101，也就是13。
     * 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
     * 返回这些数字之和。题目数据保证答案是一个 32 位 整数。
     */
    public int sumRootToLeaf(TreeNode root) {
        //思路，我们需要一次递归到叶子节点并且每次都要记录过去的val值
        return dfs(root, 0);
    }

    private static int dfs(TreeNode root, int val) {
        if (root == null) {
            return 0;
        }
        val = 2 * val + root.val;
        if (root.left == null && root.right == null) {
            return val;
        }
        return dfs(root.left, val) + dfs(root.right, val);
    }

    /**
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 如果不存在公共前缀，返回空字符串 ""。
     * <p>
     * 思路 随便先取一个做最长前缀
     * 然后无限循环判断 当前的字符串是不是由选的字符串开头的，如果不是就将开始取的字符串长度从尾部-1
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String ans = strs[0];
        for (String str : strs) {
            while (!str.startsWith(ans)) {
                if (str.length() == 0) return "";
                ans = ans.substring(0, ans.length() - 1);
            }
        }
        return ans;
    }

    //leecode  lcpone
    public int game(int[] guess, int[] answer) {
        int count = 0;
        for (int i = 0; i < guess.length; i++) {
            if (guess[i] == answer[i]) count++;
        }
        return count;
    }


    //bfs解法
    public static int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int ans = 0;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int k = queue.poll();
                    visited[k] = true;
                    for (int j = 0; j < n; j++) {
                        if (isConnected[k][j] == 1 && !visited[j]) {
                            queue.offer(j);
                        }
                    }
                }
                ans++;
            }
        }
        return ans;
    }

    public static void dfs(int[][] isConnected, int length, boolean[] visited, int j) {
        for (int k = 0; k < length; k++) {
            if (!visited[k] && isConnected[j][k] == 1) {
                visited[k] = true;
                dfs(isConnected, length, visited, k);
            }
        }
    }


    /**
     * todo leecode473  result is from the answer
     * 你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
     * 如果你能使这个正方形，则返回 true ，否则返回 false 。
     * 所有边长相等就是正方形
     */
    public boolean makesquare(int[] matchsticks) {
        int totalLen = Arrays.stream(matchsticks).sum();
        if (totalLen % 4 != 0) {
            return false;
        }
        Arrays.sort(matchsticks);
        for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
            int temp = matchsticks[i];
            matchsticks[i] = matchsticks[j];
            matchsticks[j] = temp;
        }

        int[] edges = new int[4];
        return dfs(0, matchsticks, edges, totalLen / 4);
    }

    public boolean dfs(int index, int[] matchsticks, int[] edges, int len) {
        if (index == matchsticks.length) {
            return true;
        }
        for (int i = 0; i < edges.length; i++) {
            edges[i] += matchsticks[index];
            if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)) {
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;
    }


    /**
     * 5
     * 7
     * 3 8
     * 8 1 0
     * 2 7 4 4
     * 4 5 2 6 5
     * 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。
     * 对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
     * 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。
     * 此外，向左下走的次数与向右下走的次数相差不能超过 1。
     * <p>
     * 输入描述
     * 输入的第一行包含一个整数 N\ (1 \leq N \leq 100)N (1≤N≤100)，表示三角形的行数。
     * 下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
     */
//    public static void main(String[] args) {
//        Scanner scan = new Scanner(System.in);
//        //在此输入您的代码...
//        int hang = scan.nextInt();
//        int[][] triangle = new int[hang][hang];
//        int index = 1;
//        for (int i = 0; i < hang; i++) {
//            while (index <= hang) {
//                triangle[i][index] = scan.nextInt();
//                index++;
//            }
//        }
//        //以上是赋值操作
//        for (int[] ints : triangle) {
//            for (int anInt : ints) {
//                System.out.println(anInt);
//            }
//        }
//        scan.close();
//    }

    /**
     * 小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。
     * 请计算这次考试的最高分、最低分和平均分。
     */
    public static void lanqiao497() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max = 0, min = 101, sum = 0;
        for (int i = 0; i < n; i++) {
            int cur = sc.nextInt();
            max = Math.max(cur, max);
            min = Math.min(cur, min);
            sum += cur;
        }
        System.out.println(max);
        System.out.println(min);
        float avg = (float) sum / n;
        System.out.println(sum);
        System.out.printf("%.2f", avg);
    }


    /**
     * 每个 有效电子邮件地址 都由一个 本地名 和一个 域名 组成，以 '@' 符号分隔。
     * 除小写字母之外，电子邮件地址还可以含有一个或多个'.' 或 '+' 。
     * 例如，在alice@leetcode.com中，alice是 本地名 ，而leetcode.com是 域名 。
     * 如果在电子邮件地址的 本地名 部分中的某些字符之间添加句点（'.'），则发往那里的邮件将会转发到本地名中没有点的同一地址。
     * 请注意，此规则 不适用于域名 。
     * 例如，"alice.z@leetcode.com” 和 “alicez@leetcode.com”会转发到同一电子邮件地址。
     * 如果在 本地名 中添加加号（'+'），则会忽略第一个加号后面的所有内容。这允许过滤某些电子邮件。同样，此规则 不适用于域名 。
     * 例如 m.y+name@email.com 将转发到 my@email.com。
     * 可以同时使用这两个规则。
     * 给你一个字符串数组 emails，我们会向每个 emails[i] 发送一封电子邮件。返回实际收到邮件的不同地址数目。
     */
    public static int numUniqueEmails(String[] emails) {
        Set<String> ans = new HashSet<>();
        int n = emails.length;
        StringBuilder temp = new StringBuilder();
        for (int i = 0; i < n; i++) {
            String email = emails[i];
            //做一点处理
            int at = email.indexOf("@");
            String end = email.substring(at);
            if (emails[i].contains("+")) {
                int add = email.indexOf("+");
                email = temp.append(email.substring(0, add).replace(".", "")).append(end).toString();
                ans.add(email);
                temp = new StringBuilder();
            } else {
                //说明没有+号
                //将@符号之前的内容去点
                String fix = email.substring(0, at).replace(".", "");
                email = temp.append(fix).append(end).toString();
                ans.add(email);
                temp = new StringBuilder();
            }
        }
        return ans.size();
    }


    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 请必须使用时间复杂度为 O(log n) 的算法。
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return left;
    }


    /**
     * 符合下列属性的数组 arr 称为 山脉数组 ：
     * arr.length >= 3
     * 存在 i（0 < i< arr.length - 1）使得：
     * arr[0] < arr[1] < ... arr[i-1] < arr[i]
     * arr[i] > arr[i+1] > ... > arr[arr.length - 1]
     * 给你由整数组成的山脉数组 arr
     * 返回任何满足
     * arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
     * 的下标 i 。
     */
    public static int peakIndexInMountainArray(int[] arr) {
        if (arr.length == 3) return arr[1];
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) {
                //到顶点了
                return mid;
            }
            if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                //说明答案还在右边
                left = mid;
            }
            if (arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                //答案在右边
                right = mid;
            }
        }
        return -1;
    }

    public static int peakIndexInMountainArray2(int[] arr) {
        //找数组中的最大值
        int ans = 0;
        int temp = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > temp) {
                temp = arr[i];
                ans = i;
            }
        }
        return ans;
    }


    /**
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。
     * 找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值 target，返回[-1, -1]。
     * 思路，找到最左边那个值和最右边那个值
     * <p>
     * 5,7,7,8,8,10
     */
    public static int[] searchRange2(int[] nums, int target) {
        int[] ans = new int[2];
        ans[0] = -1;
        ans[1] = -1;
        //需要先找到这个值然后从当前下标的左右开始拓展
        int numberIndex = binarySearch(nums, target);
        if (numberIndex != -1) {
            int left = numberIndex;
            int right = numberIndex;
            while (left - 1 >= 0 && nums[left - 1] == target) {
                //找到最左边的值
                left--;
            }
            while (right + 1 < nums.length && nums[right + 1] == target) {
                //找到最左边的值
                right++;
            }
            ans[0] = left;
            ans[1] = right;
            return ans;
        }
        return ans;
    }

    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                //缩小到右边区间
                left = mid + 1;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }


    /**
     * 整数数组 nums 按升序排列，数组中的值 互不相同 。
     * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
     * 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
     * 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
     * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回-1。
     */
    public int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        if (nums.length == 1) return nums[0] == target ? 0 : -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            //确定左右边界的条件是，数组第一个数字如果是小于nums[mid]的值的话，说明左边是有序的右边是无序的
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.length - 1]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[i] == target){
//                return i;
//            }
//        }
        return -1;
    }


    /**
     * 编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
     * 每行中的整数从左到右按升序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) return false;
        int n = matrix.length;
        int m = matrix[0].length;
        for (int i = 0; i < n; i++) {
            for (int i1 = 0; i1 < m; i1++) {
                if (matrix[i][i1] == target) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，
     * 原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
     * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
     * 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
     * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。
     * 请你找出并返回数组中的 最小元素 。
     * 你必须设计一个时间复杂度为O(log n) 的算法解决此问题。
     */
    public int findMin(int[] nums) {
        int min = Integer.MAX_VALUE;
//        for (int i = 0; i < nums.length; i++) {
//            min = Math.min(nums[i],min);
//        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;

        }
        return min;
    }

    /**
     * 峰值元素是指其值严格大于左右相邻值的元素。
     * 给你一个整数数组nums，找到峰值元素并返回其索引。
     * 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
     * 你可以假设nums[-1] = nums[n] = -∞ 。
     * 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
     */
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }


    /**
     * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
     * 进阶：不要 使用任何内置的库函数，如sqrt 。
     * <p>
     * 16
     * 1 2 3 4 5 6 7 8                       9 10 11 12 13 14 15 16
     */
    public boolean isPerfectSquare(int num) {
        int left = 1;
        int right = num / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long res = (long) mid * mid;
            if (res == num) {
                return true;
            }
            if (res < num) {
                left = mid + 1;
            }
            if (res > num) {
                right = mid - 1;
            }
        }
        return false;
    }

    /**
     * 给你两个整数数组arr1，arr2和一个整数d，请你返回两个数组之间的距离值。
     * 「距离值」定义为符合此距离要求的元素数目：
     * 对于元素arr1[i]，不存在任何元素arr2[j]满足 |arr1[i]-arr2[j]| <= d 。
     */
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int cnt = 0;
        for (int x : arr1) {
            int p = binarySearch2(arr2, x);
            boolean ok = true;
            if (p < arr2.length) {
                ok &= arr2[p] - x > d;
            }
            if (p - 1 >= 0 && p - 1 <= arr2.length) {
                ok &= x - arr2[p - 1] > d;
            }
            cnt += ok ? 1 : 0;
        }
        return cnt;
    }

    public int binarySearch2(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        if (arr[high] < target) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head.next == null) return head;
        if (head == null) return null;
        ListNode ans = new ListNode(0, head);
        ListNode cur = ans;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                //如果有相同的值记录这个相同的值
                int value = cur.next.val;
                //然后从cur的位置继续往下走，一直到这个值的最后一位，然后在将ans.next.next 变成这个位置
                while (cur.next != null && cur.next.val == value) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return ans.next;
    }


    /**
     * 给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，
     * 使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;
        Arrays.sort(nums); // O(nlogn)
        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去掉重复情况
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    left++;
                    right--; // 首先无论如何先要进行加减操作
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }


    /**
     * 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母target，
     * 请你寻找在这一有序列表里比目标字母大的最小字母。
     * 在比较时，字母是依序循环出现的。举个例子：
     */
    public static char nextGreatestLetter(char[] letters, char target) {
        int l = 0;
        int r = letters.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (target < letters[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return letters[l % letters.length];
    }

    /**
     * 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有piles[i]根香蕉。警卫已经离开了，将在 h 小时后回来。
     * 珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。
     * 每个小时，她将会选择一堆香蕉，从中吃掉 k 根。
     * 如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
     * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
     * 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
     */
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1, r = (int) 1e9;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(piles, mid, h)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public boolean check(int[] piles, int k, int h) {
        int cnt = 0;
        for (int pile : piles) {
            cnt += (int) Math.ceil(1.0 * pile / k);
        }
        return cnt <= h;
    }


    /**
     * 给定一个数组points，其中points[i] = [xi, yi]表示 X-Y 平面上的一个点，
     * 如果这些点构成一个回旋镖则返回true。
     * 回旋镖定义为一组三个点，这些点各不相同且不在一条
     * points.length == 3
     * points[i].length == 2
     * 0 <= xi, yi <= 100
     * 思路:
     * 根据points.length == 3
     */
    public boolean isBoomerang(int[][] points) {
        return (points[1][1] - points[0][1]) * (points[2][0] - points[1][0])
                !=
                (points[2][1] - points[1][1]) * (points[1][0] - points[0][0]);
    }


    /**
     * 小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
     * 小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
     * 对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；
     * 如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
     * 例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
     * 请计算，结点 1 和结点 2021 之间的最短路径长度是多少
     * 提示：建议使用计算机编程解决问题。\
     * <p>
     * 最小公倍数=两数的乘积/最大公约（因）数
     * 每次最多加20步
     */
    public static void lanqiao1460() {
        int n = 2022;
        int[] q = new int[n];
        q[1] = 0;
        for (int i = 2; i <= 2021; i++) {
            q[i] = Integer.MAX_VALUE;
        }
        //dp
        //当前q[j] 表示 从 1~j的最短距离
        //q[j] 可以是 当前 1~j的最短距离 或者 前一状态 到 该点的最短距离
        for (int i = 1; i <= 2020; i++)
            for (int j = i + 1; j <= 2021 && (j - i <= 21); j++) {
                q[j] = Math.min(q[j], q[i] + le(i, j));
            }

        System.out.println(q[2021]);
    }

    //最大公约数
    public static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

    //最小公倍数
    public static int le(int a, int b) {
        return a * b / gcd(a, b);
    }


    /**
     * 如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。
     * 给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
     * 返回使 s 单调递增的最小翻转次数。
     * <p>
     * 思路
     * 为了保持单调性
     * 如果当前数字是1，那他的前面的值可以是0也可以是1
     * 如果当前数字是0，那他的前面的值必须是0
     */
    public static int minFlipsMonoIncr(String s) {
        int dp0 = 0, dp1 = 0;
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            //先更新dp[i][1]，需要用到dp[i-1][0] 由于只有0和1，也不在使用三目运算
            dp1 = Math.min(dp0, dp1) + ('1' - ch);
            dp0 += ch - '0';
        }
        return Math.min(dp0, dp1);
    }


    /**
     * 给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目
     */
    public int countNegatives(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        if (n == 1) return grid[0][m - 1] < 0 ? 1 : 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] < 0) {
                    ans++;
                }
            }
        }
        return ans;
    }


    public int countNegatives2(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        if (n == 1) return grid[0][m - 1] < 0 ? 1 : 0;
        int ans = 0;

        return ans;
    }

    /**
     * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
     * 如果存在，返回 true ；否则，返回 false 。
     * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
     * <p>
     * 判断两棵树是否相同的
     * 根节点相同
     * 左子树相同
     * 右子树相同
     * <p>
     * 也就是 root.var == subroot.var && root.left.var = subroot.left.var && root.right.var = subroot.right.var
     * 且无限向下递归，直到有任意一边不同时结束循环，返回任意一种可能性
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (subRoot == null) return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot) || checkTree(root, subRoot);
    }

    private boolean checkTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;//两个都为空说明相同
        if (root == null || subRoot == null) return false;//其中一个不为空说明不相同
        //判断左子树和右子树是否一样
        if (root.val != subRoot.val) return false;
        return checkTree(root.left, subRoot.left) && checkTree(root.right, subRoot.right);
    }


    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    /*
        填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
        初始状态下，所有next 指针都被设置为 NULL。
        我们可以广度优先遍历  也就是层序遍历
        把每一个节点的next的值赋为他的右节点
        因为题目默认说了next为null，所以我们只用赋值不为空的节点的next即可
     */
    public Node connect(Node root) {
        if (root == null) return root;
        Queue<Node> queue = new LinkedList<>();
        //入队
        queue.add(root);
        //定义一个前一个节点

        while (!queue.isEmpty()) {
            //我们要获得每一层的数量
            int curLevel = queue.size();
            Node pre = null;
            for (int i = 0; i < curLevel; i++) {
                //出队,并且得到当前节点
                Node node = queue.poll();
                //如果前一个节点不为空,就将前一个节点的指向变为当前节点
                if (pre != null) {
                    pre.next = node;
                }
                //将前一个节点变为当前节点
                pre = node;
                //将当前节点的左右节点加入队列
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }

        return root;
    }


    /**
     * 学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
     * 排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
     * 给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
     * 返回满足 heights[i] != expected[i] 的 下标数量 。
     */
    public static int heightChecker(int[] heights) {
        int[] expected = new int[heights.length];
        copyAndSort(heights, expected);
        int index = 0;
        int ans = 0;
        while (index < expected.length) {
            if (heights[index] != expected[index]) ans++;
            index++;
        }
        return ans;
    }

    static void copyAndSort(int[] a1, int[] a2) {
        for (int i = 0; i < a1.length; i++) {
            a2[i] = a1[i];
        }
        Arrays.sort(a2);
    }


    /**
     * 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
     * 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，
     * 该路径同时满足下述要求：
     * 路径途经的所有单元格都的值都是 0 。
     * 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
     * 畅通路径的长度 是该路径途经的单元格总数。
     */
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) return -1;
        int n = grid.length;
        int m = grid[0].length;
        int[][] dir = {{-1, -1}, {-1, 0}, {-1, 1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {0, -1}};
        //因为每次都在找能走的路径，我们只需要广搜到图的最右下角时，就可以将结果输出
        Queue<int[]> queue = new LinkedList<>();
        //将头节点入队
        queue.add(new int[]{0, 0});
        //开始步数1
        int count = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                //出队并且得到当前节点并且判断
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];
                if (x == n - 1 && y == m - 1) return count;
                //从当前位置的八个方向进行判断入队
                for (int[] f : dir) {
                    //依次得到八个方向的值
                    int cx = x + f[0];
                    int cy = y + f[1];
                    //判断越界情况以及当前的坐标值不能为1
                    if (cx < 0 || cx >= n || cy < 0 || cy >= n || grid[cx][cy] == 1) continue;
                    //到这里说明为0并且没有越界
                    //那我们将当前节点入队
                    queue.add(new int[]{cx, cy});
                    //并且标记已经走过了
                    grid[cx][cy] = 1;
                }
            }
            //每遍历一层步数+1
            count++;

        }
        return -1;
    }


    /**
     * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     * 所有边界上的o是不会被修改为X的
     * <p>
     * 我们只需要找到矩阵中的O，然后从这个0的四周搜索,如果搜到0并且符合在边界的情况，那我们就别标记了，跳过
     * 反之，如果四周都是X那说明这个O一定会被标记
     */
    public static void solve(char[][] board) {
        int n = board.length;
        if (n == 0) return;
        int m = board[0].length;
        boolean[][] visited = new boolean[n][m];
        //边界情况，x轴为0 ,y轴为0时，y轴为数组最后一位时，x轴为数组最后一位时
        for (int i = 0; i < n; i++) {
            dfs3(visited, board, i, 0);
            dfs3(visited, board, i, m - 1);
        }
        for (int i = 0; i < m; i++) {
            dfs3(visited, board, 0, i);
            dfs3(visited, board, n - 1, i);
        }
        //标记嘛，从每个边界的O开始，标记和他相连的O
        //然后判断每一个O有没有被标记过，没有标记过的就把他变成X
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) board[i][j] = 'X';
            }
        }
    }

    private static void dfs3(boolean[][] visited, char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || visited[i][j]) {
            return;
        }
        visited[i][j] = true;
        dfs3(visited, board, i + 1, j);
        dfs3(visited, board, i - 1, j);
        dfs3(visited, board, i, j + 1);
        dfs3(visited, board, i, j - 1);
    }


    /**
     * 给你一个有n个节点的 有向无环图（DAG），请你找出所有从节点 0到节点 n-1的路径并输出（不要求按特定顺序）
     * graph[i]是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点graph[i][j]存在一条有向边）。
     */
    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> paths = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        path.add(0);
        dfs(graph, 0, path, paths);
        return paths;
    }

    // DFS回溯，cur：当前来到的位置，path：当前的DFS路径，paths：如果深度搜索到终点，形成的path加入paths
    private static void dfs(int[][] graph, int cur, LinkedList<Integer> path, List<List<Integer>> paths) {
        if (cur == graph.length - 1) { // 到达终点，收集
            paths.add(new ArrayList<>(path));
            return;
        }
        int[] nexts = graph[cur];
        for (int next : nexts) {
            path.add(next);
            dfs(graph, next, path, paths);
            path.removeLast();
        }
    }


    /**
     * 给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。
     * <p>
     * 1 2 3
     * 1    1 2 3 4
     * 2    4 5 6 5
     * 3    7 8 9 6
     * 4    1 2 3 4
     * 右（一次）  左下（遍历到越界为止） 下（一次） 右上（遍历到越界为止）
     */
    public static int[] findDiagonalOrder(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int index = 0;
        int[] ans = new int[n * m];//最终结果
        //模拟对角线  对角线的数量 = m + n -1;0
        for (int i = 0; i < m + n - 1; i++) {
            //如果当前对角线是一个偶数
            if (i % 2 == 0) {
                //要判断对角线有没有超过列数
                //x没有超过m就是i，超过了就是m-1，因为最多那么多行，你只能在最后一行
                //y没有超过m就是0，超过了就是i -m +1,因为y轴只会往后移一位
                int x = i < n ? i : n - 1;
                int y = i < n ? 0 : i - n + 1;
                //偶数我们无限向下走，直至越界，也就是，x--,y++
                while (x >= 0 && y < n) {
                    ans[index] = mat[x][y];
                    index++;
                    x--;
                    y++;
                }
            } else {
                int x = i < m ? 0 : i - m + 1;
                int y = i < m ? i : m - 1;
                //奇数我们需要往上走，直至越界也就是 x++,y--
                while (x < n && y >= 0) {
                    ans[index] = mat[x][y];
                    index++;
                    x++;
                    y--;
                }
            }
        }
        return ans;
    }


    /**
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     */
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            int all = res.size();
            for (int j = 0; j < all; j++) {
                List<Integer> tmp = new ArrayList<>(res.get(j));
                tmp.add(nums[i]);
                res.add(tmp);
            }
        }
        return res;
    }

    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        ans.add(new ArrayList<>());
        boolean[] used = new boolean[nums.length];
        dfs4(nums, ans, temp, used, 0);
        return ans;
    }


    static void dfs4(int[] nums, List<List<Integer>> ans, List<Integer> temp, boolean[] used, int begin) {
        if (!ans.contains(temp)) {
            ans.add(new ArrayList<>(temp));
        }
        for (int i = begin; i < nums.length; i++) {
            if (!temp.contains(nums[i]) && !used[i]) {
                //说明当前数字是没有用过的
                temp.add(nums[i]);
                //从当前数字开始递归寻找他的组合
                used[i] = true;
                dfs4(nums, ans, temp, used, i + 1);
                //回溯操作
                used[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
    }

    /**
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     * <p>
     * 这个题目的解题思想是这样的。由于nums内的元素存在重复，那么我们必然需要
     * 考虑如果元素重复了，怎么去处理这个元素。最直观的想法是说比如我碰到了
     * nums[i] == nums[i-1]表示当前元素我处理过了，拿题目中的数组举例子
     * nums:[1,2,2]  i=2的时候就满足上式，那么我们可以认为这个元素已经处理过了
     * 就直接跳过吗？ 显然不能 因为如果直接跳过我们就会漏掉[2,2] 和 [1,2,2]
     * 这两个组合。那么说明我们必须找出某种方式，将部分重复的元素去除。
     * 我们仔细思考一下nums[1,2,2] 当i=0的时候由于我们用于存储所有已知集合的
     * retList只含有一个[]元素，那么不存在重复问题，我们经过这一步可以得到
     * retList: [] [1] 来到2的时候我们在看 由于也不存在重复我们的2可以和
     * 之前的retlist中的元素全组合一遍得到retList:[] [1] [2] [1,2]
     * 等i=2来到这个重复的2的时候，我们发现他和前面的元素重复了，那么如果我们
     * 先不考虑重复的问题重复会得到[] [1] [2] [1,2] [2] [1,2] [2,2] [1,2,2]
     * 我们发现[2] [1,2]这部分是重复的部分是需要被踢出的部分 那么我们的目标现在
     * 就转变成了如何鉴别出引起重复的这一部分，然后在组合的时候跳过他们。我们回忆一下
     * 重复的这个[2] [1,2]来源于 2 这个元素和 [] [1] 组合导致的，因为在这个重复的
     * 2之前，已经有一个2和[] [1]发生过组合，所以这里再去组合 必然发生重复现象。
     * 那实际上这个第二次出现的2，只应该和[2] [1,2]发生组合。在这个例子中[2] [1,2]
     * 是两个组合，很容易看出来，但是我们需要一个值，来表示说出现重复时我到底该匹配的值
     * 有多少个？ 这个值就是上一次没有出现重复元素时，retList的长度。这么说太抽象了
     * 我们举个例子 假设我们来到了[] [1] 现在2要和他们进行组合 此时2和1不相同，那么
     * 他应该和整个retList进行组合 需要进行组合的元素数为2.那么当 来到第二个2时，此时
     * retList中有四个元素[] [1] [2] [1,2] 按照刚才我们说的他只可以组合两个元素，
     * 否则必然引起重复，而且是从后往前数两个元素（这个方向是因为，新的组合总是添加在数组的
     * 尾巴上），如果照我们说的 他只应该和[2],[1,2]发生组合最后的出[] [1] [2] [1,2] [2,2] [1,2,2].
     * 接下来说点别的，为什么第二个重复元素只能去和倒数的 上一次没有出现重复元素时，retList的长度个
     * 元素进行组合？
     * 原因是这样的，比如当nums[i] != num[i-1]时，此时nums[i]需要和retList中所有元素进行组合
     * 该过程完成后retList的大小会由原大小m 变化为2m。当我们继续往后走时，当前nums[i] == nums[i-1]
     * 我们直到我们当前的nums[i]只应该和之前的nums[i-1]没处理过的部分，或者之前的nums[i-1]在上一次
     * 组合中新生成的部分进行组合（否则必然造成重复），那这个新生成部分的大小是多少呢？答案是m，因为再不重复时
     * 每一次的组合结束大小都会变为原来的1倍，一半是之前的值，一半是新生成的值，而这个m就是上一次没有出现重复元素时，retList的长度。
     * 以此类推 当我们的nums[1,2,2,2] 当i=3时，这个时候他还是只需要和上一次retList的最后m个元素进行组合
     */
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<List<Integer>> retList = new ArrayList<>();
        retList.add(new ArrayList<>());
        if (nums == null || nums.length == 0) return retList;
        Arrays.sort(nums);


        List<Integer> tmp = new ArrayList<>();
        tmp.add(nums[0]);
        retList.add(tmp);
        if (nums.length == 1) return retList;

        int lastLen = 1;

        for (int i = 1; i < nums.length; i++) {
            int size = retList.size();
            if (nums[i] != nums[i - 1]) {
                lastLen = size;
            }

            for (int j = size - lastLen; j < size; j++) {
                List<Integer> inner = new ArrayList(retList.get(j));
                inner.add(nums[i]);
                retList.add(inner);
            }
        }
        return retList;
    }


    /**
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     */
    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        dfs5(temp, ans, visited, nums);
        return ans;
    }

    private static void dfs5(List<Integer> temp, List<List<Integer>> ans, boolean[] visited, int[] nums) {
        if (temp.size() == nums.length) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //最关键的代码，去重，两个数字相同，并且前一个是用过的直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            if (!visited[i]) {
                visited[i] = true;
                temp.add(nums[i]);
                dfs5(temp, ans, visited, nums);
                //回溯操作
                visited[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
    }


    /**
     * 给你一个 无重复元素 的整数数组candidates 和一个目标整数target，
     * 找出candidates中可以使数字和为目标数target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     * 对于给定的输入，保证和为target 的不同组合数少于 150 个。
     * <p>
     * 数字可以重复使用,我们先让他无限往后加，如果相加的数字大于了target就回溯并且减去之前相加的值
     * 并且我们需要一个下标来记录递归for的起使位置
     */
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        bt(ans, temp, 0, target, candidates, 0);
        return ans;
    }

    private static void bt(List<List<Integer>> ans, List<Integer> temp, int cur, int target, int[] candidates, int starIndex) {
        if (cur == target) {
            ans.add(new ArrayList<>(temp));
            return;
        } else if (cur > target) {
            //这种情况就需要回溯了
            return;
        }
        //组合问题单一集合使用变量控制循环起使位置
        for (int i = starIndex; i < candidates.length && cur + candidates[i] <= target; i++) {
            cur += candidates[i];
            temp.add(candidates[i]);
            bt(ans, temp, cur, target, candidates, i);
            //回溯
            cur -= candidates[i];
            temp.remove(temp.size() - 1);
        }
    }

//    public static void main(String[] args) {
//
//        List<List<Integer>> lists = combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
//        int i = 1;
//        for (List<Integer> list : lists) {
//            for (Integer integer : list) {
//                System.out.println(integer);
//                if (i % 3 == 0) System.out.println();
//                i++;
//            }
//        }
//    }

    /**
     * 给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
     * candidates中的每个数字在每个组合中只能使用一次。
     * 注意：解集不能包含重复的组合。
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        bt2(ans, temp, target, candidates, used, 0, 0);
        return ans;
    }

    private static void bt2(List<List<Integer>> ans, List<Integer> temp, int target, int[] candidates, boolean[] used, int sum, int startIndex) {
        if (sum == target) {
            ans.add(new ArrayList<>(temp));
        }
        if (sum > target) {
            return;
        }
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            //最重要的一句
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;
            //
            sum += candidates[i];
            used[i] = true;
            temp.add(candidates[i]);
            bt2(ans, temp, target, candidates, used, sum, i + 1);
            //回溯
            used[i] = false;
            sum -= candidates[i];
            temp.remove(temp.size() - 1);
        }
    }

    /**
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     */
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        bt3(ans, "", 0, 0, n);
        return ans;
    }

    private void bt3(List<String> ans, String s, int l, int r, int n) {
        if (l > n || r > n) return;
        if (l == n && r == n) ans.add(s);
        if (l >= r) {
            String temp = s;
            bt3(ans, temp + "(", l + 1, r, n);
            bt3(ans, temp + ")", l, r + 1, n);
        }
    }
//
//    public static void main(String[] args) {
//        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
//        exist(board, "ABCCED");
//
//    }

    /**
     * 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
     * 同一个单元格内的字母不允许被重复使用。
     */
    public static boolean res;

    public static boolean exist(char[][] board, String word) {
        if (board == null) return false;
        int n = board.length;
        int m = board[0].length;
        boolean[][] used = new boolean[n][m];
        res = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                bt4(i, j, board, word, used, 0);
            }
        }
        return res;
    }

    private static void bt4(int i, int j, char[][] board, String word, boolean[][] used, int pos) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
                used[i][j] || board[i][j] != word.charAt(pos) || res) {
            return;
        }
        if (pos == word.length() - 1) {
            res = true;
            return;
        }
        used[i][j] = true;
        //四个方向搜索
        bt4(i + 1, j, board, word, used, pos + 1);
        bt4(i, j + 1, board, word, used, pos + 1);
        bt4(i - 1, j, board, word, used, pos + 1);
        bt4(i, j - 1, board, word, used, pos + 1);
        //回溯
        used[i][j] = false;
    }

//    public static void main(String[] args) {
//        int[] arr = {3, 1, 4, 1, 5};
//        findPairs2(arr, 2);
//    }

    /**
     * 给定一个整数数组和一个整数k，你需要在数组里找到 不同的k-diff 数对，并返回不同的 k-diff 数对 的数目。
     * 这里将k-diff数对定义为一个整数对 (nums[i], nums[j])，并满足下述全部条件：
     * 0 <= i < j < nums.length
     * |nums[i] - nums[j]| == k
     * 注意，|val| 表示 val 的绝对值。
     * <p>
     * 暴力
     */
    public static int findPairs1(int[] nums, int k) {
        Arrays.sort(nums);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (Math.abs(nums[i] - nums[j]) == k) map.put(nums[i], nums[j]);
            }
        }
        return map.size();
    }

    public static int findPairs2(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = 1, pre = -(int) 1e7 - 5, ans = 0;
        while (l < nums.length && r < nums.length) {
            while (l < nums.length && nums[l] == pre) {
                l++;
            }
            if (l < nums.length) {
                while (r < nums.length && (r <= l || nums[r] - nums[l] < k)) {
                    r++;
                }
                if (r < nums.length && nums[r] - nums[l] == k) {
                    ans++;
                }
                pre = nums[l];
            }
        }
        return ans;
    }

//    public static void main(String[] args) {
//        int[] arr = {1, 3, 1, 3, 100};
//        rob(arr);
//    }

    /**
     * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，
     * 这意味着第一个房屋和最后一个房屋是紧挨着的。
     * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
     */
    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        //1  2  3  4  5  6
        //1  2  3  4  5
        //思路,因为是环形的,所以我们根据数组的长度来确定dp状态转移公式
        //区别在于你偷第一家就不能偷最后一家，偷最后一家就不可以偷第一家
        //dp[n] =max(dp[n-1] || dp[n] = dp[n-2] +nums[n-1])
        int n = nums.length;
        //我们可以将两种情况都分出来
        return Math.max(dp(Arrays.copyOfRange(nums, 0, n - 1)), dp(Arrays.copyOfRange(nums, 1, n)));
    }

    private static int dp(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = arr[0];
        for (int i = 2; i <= arr.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i - 1]);
        }
        return dp[n];
    }


    /**
     * 给定一个非负整数数组nums ，你最初位于数组的 第一个下标 。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标。
     * 2,3,1,0,4
     * 2 3 0 0 4 i == nums.length -1 true
     * <p>
     * 如果所有元素都不为0， 那么一定可以跳到最后；
     * 从后往前遍历，如果遇到nums[i] = 0，就找i前面的元素j，使得nums[j] > i - j。
     * 如果找不到，则不可能跳跃到num[i+1]，返回false。
     * //前面的元素要能跳过这个坑,不能跳过就返回false
     */
    public static boolean canJump(int[] nums) {
        int max = 0;
        int n = nums.length;
        for (int i = 0; i <= max && max < n - 1; i++) {
            max = Math.max(max, i + nums[i]);
        }
        return max >= n - 1;
    }

    /**
     * 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        for (int i = nums.length - 1; i >= 2; i--) {
            int k = 0;
            int j = i - 1;
            while (k < j) {
                //满足该条件，说明从num[k]到num[j]的数都满足要求，结果直接加上j - k
                if (nums[k] + nums[j] > nums[i]) {
                    result += j - k;
                    j--;
                } else {
                    //否则k自增，重新判断
                    k++;
                }
            }
        }
        return result;
    }


    /**
     * 给你一个长度固定的整数数组arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
     * 注意：请不要在超过该数组长度的位置写入元素。
     * 要求：请对输入的数组就地进行上述修改，不要从函数返回任何东西。
     */
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                list.add(arr[i]);
                list.add(arr[i]);
            } else {
                list.add(arr[i]);
            }
        }
        for (int i = 0; i < n; i++) {
            arr[i] = list.get(i);
        }
    }

//    public static void main(String[] args) {
////        int[] arr = {2,0,0};
//        int[] arr = {2, 3, 1, 1, 4};
//        int[] a2 = {1, 2, 3};
//        int[] a3 = {3, 2, 1};
//        int[] a4 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0};
//        System.out.println(jump(a4));
//
//    }

    /**
     * 给你一个非负整数数组nums ，你最初位于数组的第一个位置。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     * 假设你总是可以到达数组的最后一个位置。
     * 每次都跳最大一步,就是最优的跳法
     */
    public static int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int max = 0;
        int next = nums[0];
        int step = 0;
        for (int i = 0; i < nums.length; i++) {
            next = Math.max(i + nums[i], next);
            if (next >= nums.length - 1) return (step + 1);
            if (i == max) {
                step++;
                max = next;
            }
        }
        return step;
    }


    /**
     * 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
     * 问总共有多少条不同的路径？
     */
    public int uniquePaths(int m, int n) {
        //只能向下或者向右
        //f(i,j) =左边的值+上面的值 = f(i-1,j)+f(i,j-1)
        int[][] dp = new int[m][n];
        dp[0][0] = 0;
        //这个需要靠你的脑子了，你必须想到第一行和第一列，能走到的步数都为1
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 美丽的 2
     */
    public void bt2() {
        int ans = 0;
        for (int i = 0; i < 2021; i++) {
            String cur = String.valueOf(i);
            if (cur.contains("2")) {
                ans++;
            }
        }
        System.out.println(ans);
    }

    /**
     * 有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
     * 老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。 一位同学答疑的过程如下：
     * 首先进入办公室，编号为 i 的同学需要 s_i毫秒的时间。
     * 然后同学问问题老师解答，编号为 i 的同学需要 a_i毫秒的时间。
     * 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可 以忽略。
     * 最后同学收拾东西离开办公室，需要 e_i
     * 毫秒的时间。一般需要 10 秒、20 秒或 30 秒，即 e_i
     * 取值为 10000，20000 或 30000。
     * 一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。
     * 答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群 里面发消息的时刻之和最小。
     * 答疑
     */
    public static void guess() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            arr[i][0] = scanner.nextInt();
            arr[i][1] = scanner.nextInt();
            arr[i][2] = scanner.nextInt();
        }
        int min = 0;
        int count = 0;
        //使用总和排序
        Arrays.sort(arr, (a, b) -> a[0] + a[1] + a[2] - b[0] - b[1] - b[2]);
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                count += arr[i][j];
                if (j == 1) min += count;
            }
        }
        System.out.println(min);
        scanner.close();
    }


    /**
     * 给你一个二叉树的根结点root，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
     * 一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
     * <p>
     * 子树元素和 == 当前根节点的值 + 左节点的值  +  右节点的值
     */
    Map<Integer, Integer> map = new HashMap<>();
    int max = 0;

    public int[] findFrequentTreeSum(TreeNode root) {
        dfs2(root);
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
            Integer key = integerIntegerEntry.getKey();
            Integer value = integerIntegerEntry.getValue();
            if (value == max) {
                list.add(key);
            }
        }
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }


    private int dfs2(TreeNode node) {
        if (node == null) return 0;
        int sum = node.val + dfs2(node.left) + dfs2(node.right);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        max = Math.max(max, map.get(sum));
        return sum;
    }

    public String defangIPaddr(String address) {
        return address.replace(".", "[.]");
    }


    /**
     * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - (k + 1)];
        return result;
    }

    /**
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     */
    public static String longestPalindrome(String s) {
        if (s.length() == 1) return s;
        int n = s.length();
        String[] dp = new String[n];
        //每一个dp数组的元素的下标 = 他的最长回文字串为
        for (int i = 0; i < n; i++) {
            int l = i;
            int r = n - 1;
            int begin = i;
            int end = n - 1;
            while (l <= r) {
                //判断两头的元素是否相同，如果相同两个指针往中间靠拢
                //不同就清除当前下标的元素并且只移动右边元素
                if (s.charAt(l) == s.charAt(r)) {
                    l++;
                    r--;
                } else {
                    //并且还原左右指针
                    r = end - 1;
                    l = begin;
                    if (s.charAt(begin) != s.charAt(r)) {
                        r--;
                    }
                    end = r;
                }
            }
            dp[i] = s.substring(begin, end + 1);
        }
        String ans = "";
        for (int i = 0; i < dp.length; i++) {
            if (dp[i].length() > ans.length()) {
                ans = dp[i];
            }
        }
        return ans;
    }

//    public static void main(String[] args) {
//
////        System.out.println(longestPalindrome("aacabdkacaa"));
//
//        System.out.println(numberOfArithmeticSlices(new int[]{1, 2, 3, 8, 9, 10}));
//    }


    /**
     * 如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
     * <p>
     * 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
     * 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
     * 子数组 是数组中的一个连续序列。
     * 规律：
     * 除了第一层
     * 后面的每一层的数量 = 前面的层数 + 前面的最后一层的数量 +1
     * <p>
     * // 123  1
     * <p>
     * //  1234
     * // 123 234      3
     * <p>
     * //    12345
     * // 1234  2345
     * // 123 234 345    6
     * <p>
     * //    123456
     * // 12345 23456
     * // 1234 2345 3456  10
     * // 123 234 345 456
     * <p>
     * // 1234567
     * // 123456  234567
     * // 12345 23456 34567   15
     * // 1234 2345 3456 4567
     * // 123 234 345 456 567
     */
    public static int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) return 0;
        int n = nums.length;
        //每一层的数量
        int[] dp = new int[n];
        int res = 0;
        for (int i = 2; i < n; i++) {
            if ((nums[i] - nums[i - 1]) == (nums[i - 1] - nums[i - 2])) {
                dp[i] = dp[i - 1] + 1;
            }
            res += dp[i];
        }
        return res;
    }

//    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1, new TreeNode(1), null);
//        System.out.println(findBottomLeftValue(root));
//    }

    /***
     * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
     * 假设二叉树中至少有一个节点。
     *
     * 他妈的，题目是找最深节点的值,如果最深节点左边没有值，右边也会被找出来
     * 所以直接层序遍历,但是要注意，遍历从右往左遍历+
     */
    public static int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root.right != null) queue.offer(root.right);
            if (root.left != null) queue.offer(root.left);
        }
        return root.val;
    }


    /**
     * 假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
     * 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
     * 例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2]表示第 1 号房子粉刷成绿色的花费，以此类推。
     * 请计算出粉刷完所有房子最少的花费成本。
     */
    int ans = 0;

//    public static void main(String[] args) {
//        int[][] arr = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
//        System.out.println(minCost(arr));
//    }

    public int minCost(int[][] costs) {
        dfs6(costs, 4, 0);
        return ans;
    }

    /**
     * @param costs 原始数组
     * @param used  上一次被使用过的下标
     */
    private void dfs6(int[][] costs, int used, int begin) {
        if (begin < 0 || begin >= costs.length) {
            return;
        }
        //得出最小值
        int min = Integer.MAX_VALUE;
        for (int j = 0; j < costs[0].length; j++) {
            if (j == used) continue;
            if (costs[begin][j] < min) {
                //更新used
                used = j;
                min = costs[begin][j];
            }
        }
        ans += min;
        begin += 1;
        dfs6(costs, used, begin);

    }


}

class Solution {
    /**
     * 给定一个整数 n 和一个 无重复 黑名单整数数组blacklist。
     * 设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个未加入黑名单blacklist的整数。
     * 任何在上述范围内且不在黑名单blacklist中的整数都应该有 同等的可能性 被返回。
     * 优化你的算法，使它最小化调用语言 内置 随机函数的次数。
     * 实现Solution类:
     * Solution(int n, int[] blacklist)初始化整数 n 和被加入黑名单blacklist的整数
     * int pick()返回一个范围为 [0, n - 1] 且不在黑名单blacklist 中的随机整数
     */
    Map<Integer, Integer> b2w;
    Random random;
    int bound;

    public Solution(int n, int[] blacklist) {
        b2w = new HashMap<Integer, Integer>();
        random = new Random();
        int m = blacklist.length;
        bound = n - m;
        Set<Integer> black = new HashSet<Integer>();
        for (int b : blacklist) {
            if (b >= bound) {
                black.add(b);
            }
        }

        int w = bound;
        for (int b : blacklist) {
            if (b < bound) {
                while (black.contains(w)) {
                    ++w;
                }
                b2w.put(b, w);
                ++w;
            }
        }
    }

    public int pick() {
        int x = random.nextInt(bound);
        return b2w.getOrDefault(x, x);
    }

    /**
     * 请你帮忙给从 1 到 n的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；
     * 你需要返回可能的方案总数。
     * 让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
     * 由于答案可能会很大，所以请你返回答案 模 mod10^9 + 7之后的结果即可。
     */
    public int numPrimeArrangements(int n) {
        int sum = 0;
        if (n > 2) {
            sum = fun(n);
        } else {
            return 1;
        }
        long cur = 1L;
        for (int i = 2; i <= sum; i++) {
            cur = (cur * i) % (1000000000 + 7);
        }
        for (int i = 2; i <= n - sum; i++) {
            cur = (cur * i) % (1000000000 + 7);
        }
        return (int) cur;
    }

    public int fun(int n) {
        n += 1;
        int sum = 0;
        boolean[] bool = new boolean[n + 1];
        for (int i = 2; i < n; i++) {
            if (bool[i] == false) {
                sum++;
                for (int j = 2; j * i < n; j++) {
                    bool[j * i] = true;
                }
            }
        }
        return sum;
    }

    Map<String, List<Integer>> map = new HashMap<>();

    public List<Integer> diffWaysToCompute(String expression) {
        // 记录已经计算出来的字符串对应的值，避免重复计算。
        if (map.containsKey(expression)) return map.get(expression);
        List<Integer> list = new ArrayList<>();
        int len = expression.length();
        for (int i = 0; i < len; i++) {
            char c = expression.charAt(i);
            if (c == '+' || c == '-' || c == '*') {  // 出现运算符号，递归求解前半段和后半段。
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                // -1   =>  left:[[0]]  right:[[1]]
                for (int l : left) {
                    for (int r : right) {
                        switch (c) {
                            case '+':
                                list.add(l + r);
                                break;
                            case '-':
                                list.add(l - r);
                                break;
                            case '*':
                                list.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        if (list.size() == 0) list.add(Integer.valueOf(expression));
        // 单独一个数字的情况 (可能出现多位数)
        map.put(expression, list);
        return list;
    }

//    public static void main(String[] args) {
//        int[] arr = {4, 2, 1, 3};
//        List<List<Integer>> lists = minimumAbsDifference(arr);
//        for (List<Integer> list : lists) {
//            for (Integer integer : list) {
//                System.out.println(integer);
//            }
//        }
//    }

    //超时暴力写法

    /**
     * 给你个整数数组 arr，其中每个元素都 不相同。
     * 请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
     */
    public static List<List<Integer>> minimumAbsDifference(int[] arr) {
        int min = Integer.MAX_VALUE;
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(arr);
        for (int i = 0, j = 1; i < arr.length && j < arr.length; i++, j++) {
            //得到最小差
            int abs = Math.abs(arr[i] - arr[j]);
            if (abs < min) {
                min = abs;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (Math.abs(arr[i] - arr[j]) == min) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(arr[i]);
                    temp.add(arr[j]);
                    ans.add(new ArrayList<>(temp));
                    break;
                }
            }
        }
        return ans;
    }

    //一次遍历
    public List<List<Integer>> minimumAbsDifference2(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> ans = new ArrayList<>();
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length - 1; ++i) {
            if (arr[i + 1] - arr[i] == min) {
                ans.add(Arrays.asList(arr[i], arr[i + 1]));
            } else if (arr[i + 1] - arr[i] < min) {
                ans.clear();
                ans.add(Arrays.asList(arr[i], arr[i + 1]));
                min = arr[i + 1] - arr[i];
            }
        }
        return ans;
    }

//    public static void main(String[] args) {
//        MyCalendar calendar = new MyCalendar();
//        //[[],[48,50],[0,6],[6,13],[8,13],[15,23],[49,50],[45,50],[29,34],[3,12],[38,44]]
//        calendar.book(48, 50);
//        calendar.book(0, 6);
//        calendar.book(6, 13);
//        calendar.book(15, 23);
//        calendar.book(49, 50);
//        calendar.book(45, 50);
//        calendar.book(29, 34);
//        calendar.book(3, 12);
//        calendar.book(38, 44);
//    }


//    public static void main(String[] args) {
//        int[] arr = {2, 3, -1, 4};
//        maxProduct(arr);
//    }

    /**
     * 给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
     * 测试用例的答案是一个32-位 整数。
     * 子数组 是数组的连续子序列。
     */
    public static int maxProduct(int[] nums) {
        int result = nums[0], a = 1;
        for (int i = 0; i < nums.length; i++) {
            a = a != 0 ? a * nums[i] : nums[i];
            result = Math.max(result, a);
        }
        a = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            a = a != 0 ? a * nums[i] : nums[i];
            result = Math.max(result, a);
        }
        return result;
    }


    /**
     * 给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
     */
    public int removeElement(int[] nums, int val) {
        int ans = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                nums[i] = 51;
                ans--;
            }
        }
        Arrays.sort(nums);
        return ans;
    }


    /**
     * 对于一个正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。
     * 给定一个整数n，如果是完美数，返回 true；否则返回 false。
     */
    public static boolean checkPerfectNumber(int num) {
        int ans = 0;
        for (int i = 1; i < num; i++) {
            if (num % i == 0) {
                ans += i;
            }
        }
        return ans == num;
    }

//    public static void main(String[] args) {
////        int[][] arr = {{4, 8},{5,49}};
//        int[][] arr = {{10, 10}};
//        System.out.println(calculateTax(arr, 5));
//    }

    /**
     * 给你一个下标从 0 开始的二维整数数组 brackets
     * ，其中 brackets[i] = [upperi, percenti] ，表示第 i 个税级的上限是 upperi ，征收的税率为 percenti 。
     * 税级按上限 从低到高排序（在满足 0 < i < brackets.length 的前提下，upperi-1 < upperi）。
     */
    public static double calculateTax(int[][] brackets, int income) {
        if (income == 0) return 0.0;
        int n = brackets.length;
        if (n == 1 && brackets[0][0] > income) {
            return income * 1.0 * (brackets[0][1] * 1.00 / 100);
        }
//        double ans = (double) brackets[0][0] * brackets[0][1] / 100;
        double ans = 0.00;
        int pre = 0;
        for (int i = 0; i < n; i++) {
            if (income < brackets[i][0]) {
                //直接拿当前数字去剪然后乘以税率
                ans += (double) (income - pre) * (brackets[i][1] * 1.00 / 100);
                break;
            } else {
                ans += (double) (brackets[i][0] - pre) * (brackets[i][1] * 1.00 / 100);
                pre = brackets[i][0];
            }
        }
        //这里还要再做一次运算
        return ans;
    }

    /**
     * 在英语中，我们有一个叫做词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为继承词(successor)
     * 例如，词根an，跟随着单词other(其他)，可以形成新的单词another(另一个)。
     * 现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。
     * 你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
     * 你需要输出替换之后的句子
     */
    public String replaceWords(List<String> dictionary, String sentence) {
        StringBuilder ans = new StringBuilder();
        String[] temp = sentence.split(" ");
        for (int i = 0; i < temp.length; i++) {
            for (String s : dictionary) {
                if (temp[i].startsWith(s)) {
                    temp[i] = s;
                }
            }
            ans.append(temp[i]).append(" ");
        }
        return ans.toString().trim();
    }


    /**
     * 给你两个正整数n 和k。
     * 如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n的因子。
     * 考虑整数 n的所有因子，将它们 升序排列。请你返回第 k个因子。如果 n的因子数少于 k，请你返回 -1。
     */
    public static int kthFactor(int n, int k) {
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                k--;
            }
            if (k == 0) return i;
        }
        return -1;
    }

//    public static void main(String[] args) {
////        int[] arr = {2,21,43,38,0,42,33,7,24,13,12,27,12,24,5,23,29,48,30,31};
////        int[] arr2 = {2,42,38,0,43,21};
////        for (int i : relativeSortArray(arr, arr2)) {
////            System.out.println(i);
////        }
////    }

    /**
     * 给你两个数组，arr1 和arr2，arr2中的元素各不相同，arr2 中的每个元素都出现在arr1中。
     * 对 arr1中的元素进行排序，使 arr1 中项的相对顺序和arr2中的相对顺序相同。
     * 未在arr2中出现过的元素需要按照升序放在arr1的末尾。
     */
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int[] ans = new int[n];
        int[] temp = new int[1001];
        Arrays.sort(arr1);
        for (int i : arr1) {
            temp[i]++;
        }
        int index = 0;
        for (int i = 0; i < arr2.length; i++) {
            if (temp[arr2[i]] == 0) {

            } else {
                while (temp[arr2[i]] != 0) {
                    temp[arr2[i]]--;
                    ans[index] = arr2[i];
                    index++;
                }
            }
        }
        for (int i = 0; i < temp.length; i++) {
            while (temp[i] != 0) {
                ans[index] = i;
                temp[i]--;
                index++;
            }
        }
        return ans;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外，这两个数都不会以 0开头。
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    //5 10 15  20
//    public static void main(String[] args) {
//        BigInteger bigInteger = new BigInteger("1");
//        for (int i = 1; i <= 30; i++) {
//            bigInteger = bigInteger.multiply(BigInteger.valueOf(i));
//            System.out.println(i + " " + bigInteger);
//        }
//        int ans = 0;
//        for (int length = bigInteger.toString().length(); length > 0; length--) {
//            if (bigInteger.toString().charAt(length - 1) == '0') ans++;
//            else break;
//        }
//        System.out.println(ans);
//    }

    /**
     * 设计一个算法，算出 n 阶乘有多少个尾随零。
     * <p>
     * <p>
     * 找规律
     * 每一个0 = 2 * 5
     */
    public int trailingZeroes(int n) {
        if (n < 5) return 0;
        int ans = 0;
        while (n >= 5) {
            n /= 5;
            ans += n;
        }
        return ans;
    }

//    public static void main(String[] args) {
//        uniqueOccurrences(new int[]{1, 2, 2, 1, 1, 3});
//    }

    public static boolean uniqueOccurrences(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], 1);
            } else {
                map.replace(arr[i], map.get(arr[i]), map.get(arr[i]) + 1);
            }
        }
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : set) {
            if (list.contains(entry.getValue())) return false;
            else list.add(entry.getValue());
        }
        return true;
    }


    /**
     * 有n个筹码。第 i 个筹码的位置是position[i]。
     * 我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个筹码的位置从position[i]改变为:
     * position[i] + 2或position[i] - 2，此时cost = 0
     * position[i] + 1或position[i] - 1，此时cost = 1
     * 返回将所有筹码移动到同一位置上所需要的 最小代价
     */
    public int minCostToMoveChips(int[] position) {
        int t1 = 0, t2 = 0, ans = 0;
        for (int i = 0; i < position.length; i++) {
            if (position[i] % 2 == 0) t1++;
            else t2++;
        }
        if (t1 < t2) {
            ans = t1;
        } else ans = t2;
        return ans;
    }

//    public static void main(String[] args) {
//        firstUniqChar("loveleetcode");
//    }

    //给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1
    public static int firstUniqChar(String s) {
        if (s.length() == 1) return 0;
        Set<Character> set = new HashSet<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[j] != chars[i] && j == s.length() - 1 && !set.contains(chars[i])) {
                    return i;
                } else if (chars[i] == chars[j]) {
                    set.add(chars[i]);
                    break;
                }
            }
            if (i == s.length() - 1 && !set.contains(s.charAt(i))) {
                return i;
            }
        }
        return -1;
    }

//    public static void main(String[] args) {
//        System.out.println(getNumberWithMedium(28561));
//    }

    public static int getNumberWithMedium(int n) {
        int t = n;
        while (0 <= t) {
            if (t <= 500) break;
            else t /= 2;
        }
        return t;
    }

//    public static void main(String[] args) {
//        oddCells(2, 3, new int[][]{{0, 1}, {1, 1}});
//
//    }

    /**
     * 给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。
     * 另有一个二维索引数组indices，indices[i] = [ri, ci] 指向矩阵中的某个位置，其中 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。
     * 对 indices[i] 所指向的每个位置，应同时执行下述增量操作：
     * ri 行上的所有单元格，加 1 。
     * ci 列上的所有单元格，加 1 。
     * 给你 m、n 和 indices 。请你在执行完所有indices指定的增量操作后，返回矩阵中 奇数值单元格 的数目。
     */
    public static int oddCells(int m, int n, int[][] indices) {
        int ans = 0;
        int in = indices.length;
        int[][] temp = new int[m][n];
        for (int i = 0; i < in; i++) {
            int ri = indices[i][0];
            int ci = indices[i][1];
            for (int j = 0; j < n; j++) {
                temp[ri][j]++;
            }
            for (int k = 0; k < m; k++) {
                temp[k][ci]++;
            }
        }
        for (int[] ints : temp) {
            for (int anInt : ints) {
                if (anInt % 2 != 0 && anInt != 0) {
                    ans++;
                }
            }
        }
        return ans;
    }


    /**
     * 给定一个整数数组 asteroids，表示在同一行的行星。
     * 对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
     * 找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。
     * 如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
     */
    public int[] asteroidCollision(int[] asteroids) {
        //爆炸的前提 是   左边的数字大于0  右边的数字小于0 否则跳过
        Deque<Integer> stack = new LinkedList();
        for (int i = 0; i < asteroids.length; i++) {
            int num = asteroids[i];
            //判断当前遍历到的元素是否爆炸，如果爆炸就不需要入栈
            boolean flag = false;
            while (!stack.isEmpty() && stack.getLast() > 0 && num < 0) {
                int last = stack.getLast();
                if (Math.abs(asteroids[i]) > last) stack.pollLast();
                else if (Math.abs(asteroids[i]) < last) {
                    flag = true;
                    break;
                } else {
                    stack.pollLast();
                    flag = true;
                    break;
                }
            }
            if (!flag) stack.addLast(num);
        }
        int[] res = new int[stack.size()];
        int index = 0;
        while (!stack.isEmpty()) res[index++] = stack.pollFirst();
        return res;
    }


//    public static void main(String[] args) {
//        MagicDictionary magicDictionary = new MagicDictionary();
//        magicDictionary.buildDict(new String[]{"hello", "leetcode", "judge"});
//        System.out.println(magicDictionary.search("hello"));
//        System.out.println(magicDictionary.search("hallo"));
//        System.out.println(magicDictionary.search("hell"));
//        System.out.println(magicDictionary.search("leetcodd"));
//        System.out.println(magicDictionary.search("juage"));
//    }


    /**
     * 在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
     * 给你一个平衡字符串s，请你将它分割成尽可能多的平衡字符串。
     * 注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
     * 返回可以通过分割得到的平衡字符串的 最大数量 。
     * <p>
     * L 76    R 82
     */
    public static int balancedStringSplit(String s) {
        int left = 0, right = 0, ans = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'L') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                ans++;
                left = 0;
                right = 0;
            }
        }
        return ans;
    }

    /**
     * 有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。
     * 给你一个二维整数数组 edges ，其中edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。
     * 请你找出并返回edges 所表示星型图的中心节点。
     */
    public int findCenter(int[][] edges) {
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            if (!map.containsKey(x)) {
                map.put(x, 1);
            } else {
                map.replace(x, map.get(x), map.get(x) + 1);
            }
            if (!map.containsKey(y)) {
                map.put(y, 1);
            } else {
                map.replace(y, map.get(y), map.get(y) + 1);
            }
        }
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            Integer key = e.getKey();
            Integer value = e.getValue();
            if (value > ans) {
                ans = value;
                ans = key;
            }
        }
        return ans;
    }

    public int findCenter2(int[][] edges) {
        int max = 0;
        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < edges[i].length; j++) {
                max = Math.max(edges[i][j], max);
            }
        }
        int[] arr = new int[max];
        for (int i = 0; i < edges.length; i++) {
            arr[edges[i][0]]++;
            arr[edges[i][1]]++;
        }
        int temp = 0;
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > temp) {
                temp = arr[i];
                ans = i;
            }
        }
        return ans;
    }

    public static int findCenter3(int[][] edges) {
        return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1] ? edges[0][0] : edges[0][1];
    }

    public int mostWordsFound(String[] sentences) {
        int ans = 0;
        for (String sentence : sentences) {
            String[] s = sentence.split(" ");
            ans = Math.max(s.length, ans);
        }
        return ans;
    }

    //思路：两个数组相对匹配
    public boolean isLongPressedName(String name, String typed) {

        return false;
    }

    /*
    索引从0开始长度为N的数组A，包含0到N - 1的所有整数。
    找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
    假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
     */
    public int arrayNesting(int[] nums) {
        int max = 1;
        boolean[] visited = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (max > nums.length / 2)
                return max;
            if (visited[nums[i]])
                continue;
            visited[nums[i]] = true;
            int curMax = 1;
            int cur = nums[nums[i]];
            while (nums[i] != cur) {
                visited[cur] = true;
                curMax++;
                cur = nums[cur];
            }
            max = Math.max(curMax, max);
        }
        return max;
    }

    /**
     * 给你一个以行程长度编码压缩的整数列表nums。
     * 考虑每对相邻的两个元素 [freq, val] = [nums[2*i], nums[2*i+1]]（其中i >= 0），
     * 每一对都表示解压后子列表中有 freq个值为val的元素，你需要从左到右连接所有子列表以生成解压后的列表。
     * 请你返回解压后的列表。
     */
    public int[] decompressRLElist(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < nums.length; i += 2) {
            for (int j = 0; j < nums[i - 1]; j++) {
                list.add(nums[i]);
            }
        }
        int[] arr = new int[list.size()];
        int index = 0;
        for (Integer i : list) {
            arr[index] = i;
            index++;
        }
        return arr;
    }


    /**
     * 给你一个数组candies和一个整数extraCandies，其中candies[i]代表第 i 个孩子拥有的糖果数目。
     * 对每一个孩子，检查是否存在一种方案，将额外的extraCandies个糖果分配给孩子们之后，
     * 此孩子有 最多的糖果。注意，允许有多个孩子同时拥有 最多的糖果数目。
     */
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int max = 0;
        List<Boolean> list = new ArrayList<>();
        //检索最大的那个孩子出来并且直接赋值
        for (int i = 0, j = candies.length - 1; i < candies.length && j >= 0; i++, j--) {
            int a = Math.max(candies[i], candies[j]);
            max = Math.max(a, max);
        }
        for (int candy : candies) {
            if (candy + extraCandies >= max) {
                list.add(true);
            } else list.add(false);
        }
        return list;
    }

//    public static void main(String[] args) {
//        for (int i = 1; i <= 120; i++) {
//            if (i % 2 != 0) {
//                System.out.println(i);
//            }
//            if (i % 10 == 1 && i != 1) System.out.println();
//        }
//    }

    List<Integer> ans = new LinkedList<>();

    public List<Integer> inorderTraversal(EDayExam.TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            ans.add(root.val);
            inorderTraversal(root.right);
        }
        return ans;
    }

    /**
     * 给定一个包含大写字母和小写字母的字符串s，返回通过这些字母构造成的 最长的回文串。
     * 在构造过程中，请注意 区分大小写 。比如"Aa"不能当做一个回文字符串
     * A -Z  65 - 90
     * a -z  97 - 122
     */
    public int longestPalindrome(String s) {
        int[] low = new int[26];
        int[] up = new int[26];
        char[] array = s.toCharArray();
        int n = array.length, ans = 0;
        for (int i = 0; i < n; i++) {
            if (array[i] > 90) {
                low[array[i] - 'a']++;
            } else {
                up[array[i] - 'A']++;
            }
        }
        boolean flag = false;
        for (int i = 0; i < 26; i++) {
            if (low[i] % 2 == 0) {
                ans += low[i];
            } else {
                flag = true;
                ans += (low[i] - 1);
            }
            if (up[i] % 2 == 0) {
                ans += up[i];
            } else {
                flag = true;
                ans += (up[i] - 1);
            }
        }
        if (flag) ans += 1;
        return ans;
    }

    //low 和 high 都为偶数时 == (high -low )/2
    //else   (high -low)/2 +1
    public int countOdds(int low, int high) {
        return low % 2 == 0 && high % 2 == 0 ? (high - low) / 2 : (high - low) / 2 + 1;
    }


    /**
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     */
    public int lengthOfLongestSubstring(String s) {
        int length = s.length();
        int max = 0;//存储最大的长度
        int left = 0;//最左边的指针
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < length; i++) {
            //先判断要加入的字符存在map中是否
            if (map.containsKey(s.charAt(i))) {
                //存在的话,需要将最左边的指针移到当前字符的后一位 也就是i +1
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            //更新max的值,比较一下之前的max和现在的max谁大，谁大max就是谁
            //现在的max的值怎么算呢？  当前字符的下标-存储下标left 的值+1
            max = Math.max(max, i - left + 1);
        }
        return max;
    }


    public int reverse(int x) {
        String s = String.valueOf(x);
        List<Character> list = new ArrayList<>();
        if (s.contains("-")) {
            s.replace("-", "");
            char[] chars = s.toCharArray();
            for (char aChar : chars) {
                list.add(aChar);
            }
            Collections.reverse(list);
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append("-");
            for (Character c : list) {
                stringBuilder.append((int) c);
            }
            return Integer.parseInt(stringBuilder.toString());
        } else {
            char[] chars = s.toCharArray();
            for (char aChar : chars) {
                list.add(aChar);
            }
            Collections.reverse(list);
            StringBuilder stringBuilder = new StringBuilder();
            for (Character c : list) {
                stringBuilder.append((int) c);
            }
            return Integer.parseInt(stringBuilder.toString());
        }
    }


    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] t1 = new boolean[m];
        boolean[] t2 = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    t2[j] = true;
                    t1[i] = true;
                }
            }
        }
        for (int i = 0; i < t2.length; i++) {
            if (t2[i]) {
                int index = 0;
                while (index < m) {
                    matrix[index][i] = 0;//标记
                    index++;
                }
            }
        }
        for (int i = 0; i < t1.length; i++) {
            if (t1[i]) setZero(matrix, i);
        }
    }

    static void setZero(int[][] matrix, int h) {
        int index = 0;
        while (index < matrix[0].length) {
            matrix[h][index] = 0;//标记
            index++;
        }
    }


    //超时
    public static int smallestDifference(int[] a, int[] b) {
        int n = a.length;
        int m = b.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < m; k++) {
                int abs = Math.abs(a[i] - b[k]);
                if (abs < 0) {
                    continue;
                }
                min = Math.min(abs, min);
            }
        }
        return min;
    }

    public int prefixCount(String[] words, String pref) {
        int ans = 0;
        for (String s : words) {
            if (s.startsWith(pref)) ans++;
        }
        return ans;
    }

    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        return Arrays.copyOfRange(arr, 0, k);
    }

    public int[] sortArrayByParity(int[] nums) {
        if (nums.length == 1) return nums;
        int[] ans = new int[nums.length];
        int begin = 0;
        int end = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                ans[begin] = nums[i];
                begin++;
            } else {
                ans[end] = nums[i];
                end--;
            }
        }
        return ans;
    }

    /**
     * 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
     * 给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案对10的9次方 + 7 取模后的值。
     */
    public int nthMagicalNumber(int n, int a, int b) {
        BigInteger number = new BigInteger("10").pow(9).add(new BigInteger("7"));
        return new BigInteger(String.valueOf(a)).pow(n).mod(number).intValue();
    }


    /**
     * 给你一个整数数组arr ，请你将数组中的每个元素替换为它们排序后的序号。
     * 序号代表了一个元素有多大。序号编号的规则如下：
     * 序号从 1 开始编号。
     * 一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
     * 每个数字的序号都应该尽可能地小。
     */
    public static int[] arrayRankTransform(int[] arr) {
        int[] ans = new int[arr.length];
        Map<Integer, Integer> map = new HashMap<>();
        int[] copy = Arrays.copyOf(arr, arr.length);
        Arrays.sort(arr);
        int index = 1;
        for (int i = 0; i < arr.length; i++) {
            if (!map.containsKey(arr[i])) {
                map.put(arr[i], index);
                index++;
            }
        }
        for (int i = 0; i < copy.length; i++) {
            ans[i] = map.get(copy[i]);
        }
        return ans;
    }


    public static int countWords(String[] words1, String[] words2) {
        int ans = 0;
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        List<String> t1 = new ArrayList<>();
        List<String> t2 = new ArrayList<>();
        for (String s : words1) {
            if (map.containsKey(s)) {
                map.replace(s, map.get(s) + 1);
            } else map.put(s, 1);
        }
        for (String s : words2) {
            if (map2.containsKey(s)) {
                map2.replace(s, map2.get(s) + 1);
            } else map2.put(s, 1);
        }
        for (Map.Entry<String, Integer> stringIntegerEntry : map.entrySet()) {
            if (stringIntegerEntry.getValue() == 1) {
                t1.add(stringIntegerEntry.getKey());
            }
        }
        for (Map.Entry<String, Integer> stringIntegerEntry : map2.entrySet()) {
            if (stringIntegerEntry.getValue() == 1) {
                t2.add(stringIntegerEntry.getKey());
            }
        }
        if (t1.size() > t2.size()) {
            for (String s : t2) {
                if (t1.contains(s)) {
                    ans++;
                }
            }
        } else {
            for (String s : t1) {
                if (t2.contains(s)) ans++;
            }
        }
        return ans;
    }

    /*
    []
    []
     */


    /**
     * 给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
     * 请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。
     */
    public static int dominantIndex(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        Arrays.sort(nums);
        main:
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] + nums[j] > nums[i]) break main;
                if (nums[j] + nums[j] <= nums[i]) return map.get(nums[i]);
            }
        }
        return -1;
    }

    //从上面的代码可以看出来，我们不需要将最大值和所有元素比较
    //只需要将第二大的元素乘以2去比较最大的值,如果超过就返回-1,如果小于等于就返回我们记录的下标即可
    public static int dominantIndex2(int[] nums) {
        int max = 0, second = 0, index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                second = max;
                max = nums[i];
                index = i;
            } else if (nums[i] > second) {

                second = nums[i];
            }
        }
        return second * 2 <= max ? index : -1;
    }

    int x = 0, nums = 0;

    public String solveEquation(String equation) {
        int e = equation.lastIndexOf('='), n = equation.length();
        deal(equation.substring(0, e).toCharArray(), true);
        deal(equation.substring(e + 1, n).toCharArray(), false);
        if (x == 0 && nums == 0) return "Infinite solutions";
        else if (x == 0 && nums != 0) return "No solution";
        return "x=" + (-nums / x) + "";
    }

    public void deal(char[] ss, boolean f) {
        int n = ss.length;
        String equation = String.valueOf(ss, 0, n);
        for (int i = 0; i < n; ) {
            //先判断负号
            if (ss[i] == '-') {
                int j = i + 1;
                if (ss[j] == 'x') {
                    x += f ? -1 : 1;
                    i = j + 1;
                } else {
                    while (j < n && Character.isDigit(ss[j])) j++;
                    int k = Integer.parseInt(equation.substring(i + 1, j));
                    if (j < n && ss[j] == 'x') {
                        x += f ? -k : k;
                        i = j + 1;
                    } else {
                        nums += f ? -k : k;
                        i = j;
                    }
                }
                continue;
            } else if (ss[i] == 'x') {
                x += f ? 1 : -1;
                i++;
                continue;
            } else if (Character.isDigit(ss[i])) {
                int j = i + 1;
                while (j < n && Character.isDigit(ss[j])) j++;
                int k = Integer.parseInt(equation.substring(i, j));
                if (j < n && ss[j] == 'x') {
                    x += f ? k : -k;
                    i = j + 1;
                } else {
                    nums += f ? k : -k;
                    i = j;
                }
                continue;
            } else {
                i++;
            }
        }
    }

    /**
     * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
     */
    public String removeDuplicateLetters(String s) {
        char[] chars = s.toCharArray();

        return null;
    }

    public int numOfStrings(String[] patterns, String word) {
        int ans = 0;
        for (String pattern : patterns) {
            if (word.contains(pattern)) ans++;
        }
        return ans;
    }

    public int sumOddLengthSubarrays(int[] arr) {
        if (arr == null || arr.length == 1) return arr[0];
        int n = arr.length;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum = sum + arr[i] * ((i / 2 + 1) * ((n - i - 1) / 2 + 1) + ((i + 1) / 2) * ((n - i) / 2));
        }
        return sum;
    }

    public int maxNumberOfBalloons(String text) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();

        char[] ss = text.toCharArray();

        for (int i = 0; i < ss.length; i++) {
            map.put(ss[i], map.getOrDefault(ss[i], 0) + 1);
        }

        int res = 0;
        int b = map.getOrDefault('b', 0);
        int a = map.getOrDefault('a', 0);
        int l = map.getOrDefault('l', 0);
        int o = map.getOrDefault('o', 0);
        int n = map.getOrDefault('n', 0);

        int count1 = Math.min(Math.min(b, a), n);
        int count2 = Math.min(l / 2, o / 2);
        return Math.min(count1, count2);
    }


    /**
     * 给你一个混合了数字和字母的字符串 s，其中的字母均为小写英文字母。
     * 请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。
     * 请你返回 重新格式化后 的字符串；如果无法按要求重新格式化，则返回一个 空字符串 。
     */
    public static String reformat(String s) {
        if (s.length() == 1) return s;
        char[] chars = s.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();
        List<Character> cs = new ArrayList<>();
        List<Character> ints = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            //97 - 122
            if (chars[i] >= 97 && chars[i] <= 122) {
                cs.add(chars[i]);
            } else {
                ints.add(chars[i]);
            }
        }
        if (cs.size() == 0 || ints.size() == 0) return "";
        if (cs.size() - ints.size() > 1 || ints.size() - cs.size() > 1) return "";
        int ci = 0, ii = 0;
        boolean flag = true;
        if (cs.size() > ints.size()) {
            while (ci < cs.size() || ii < ints.size()) {
                if (flag) {
                    stringBuilder.append(cs.get(ci));
                    ci++;
                    flag = false;
                } else {
                    stringBuilder.append(ints.get(ii));
                    ii++;
                    flag = true;
                }
            }
        } else {
            while (ci < cs.size() || ii < ints.size()) {
                if (flag) {
                    stringBuilder.append(ints.get(ii));
                    ii++;
                    flag = false;
                } else {
                    stringBuilder.append(cs.get(ci));
                    ci++;
                    flag = true;
                }
            }
        }
        return stringBuilder.toString();
    }


//    public static void main(String[] args) {
////        isStraight(new int[]{11,8,12,8,10});//0,0,1,2,5  []
////        isStraight(new int[]{1, 2, 3, 4, 5});//0,0,1,2,5  [] 003567
//
//        isStraight2(new int[]{10, 11, 0, 12, 6});//0,0,1,2,5  [][]
//    }

    /**
     * 从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
     * ac但是复杂度较高
     */
    public static boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count++;
            } else break;
        }
        if (count == 4) return true;
        if (count == 3) return nums[4] - nums[3] <= count;
        if (count == 0) {
            int index = 0;
            while (index < nums.length - 1) {
                if (nums[index] + 1 != nums[index + 1]) return false;
                index++;
            }
            return true;
        } else {
            //01345
            //00125
            int temp = 0;
            for (int i = nums.length - 1; i > count; i--) {
                if (nums[i] == nums[i - 1]) return false;
                temp += nums[i] - nums[i - 1] - 1;
            }
            return temp <= count;
        }
    }

    //第二种解放  如果数字有重复 那直接返回false,如果没有0，最小值和最大值的差一定是4
    //其它情况不管有多少个0，只要最小值和最大值的差小于等于4即可
    public static boolean isStraight2(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0) count++;
            else if (nums[i] == nums[i + 1]) return false;
        }
        //000911
        if (count == 0) return nums[4] - nums[0] == 4;
        return nums[4] - nums[count] <= 4;
    }


//    public static void main(String[] args) {
//
//        int[] arr = new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1};
//        System.out.println(arr.length * (arr.length + 1) / 2);//公式  求出 1-n的和
//    }

    /**
     * 在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
     * 当提莫攻击艾希，艾希的中毒状态正好持续duration 秒。
     * 正式地讲，提莫在 t 发起发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。
     * 给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。
     * 返回艾希处于中毒状态的 总 秒数。
     */
    public static int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 1) {
            return duration;
        }
        int ans = 0;
        for (int i = 0; i < timeSeries.length - 1; i++) {
            ans += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
        }
        return ans + duration;
    }

    /*
    数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
     */
    public int missingNumber(int[] nums) {
//        return nums.length * (nums.length+1)/2 - Arrays.stream(nums).sum();
        int n = nums.length;
        int sum = n * (n + 1) / 2;//求出1-n的总和
        int count = 0;
        for (int i : nums) {
            count += i;
        }
        return sum - count;
    }

    /*
    将矩阵按照对角线对调
    123
    456
    789

    147
    258
    369
     */
    public int[][] transpose(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] ans = new int[m][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[j][i] = matrix[i][j];
            }
        }
        return ans;
    }


    /**
     * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
     * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
     */
    public static int[][] findContinuousSequence(int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> box = new ArrayList<>();
        int t = target / 2 + 1;
        int count = 0;
        for (int i = t; i > 0; i--) {
            box = new ArrayList<>();
            count = 0;
            for (int j = i; j > 0; j--) {
                if (count == target) {
                    //重置
                    list.add(box);
                    break;
                } else {
                    box.add(j);
                    count += j;
                }
            }
        }
        int[][] ans = new int[list.size()][1000];
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.get(i).size(); j++) {
                ans[i][j] = list.get(i).get(j);
            }
        }
        return ans;
    }

    //数字2出现的次数
    public int numberOf2sInRange(int n) {
        int ans = 1;
        for (int i = 3; i < n; i++) {
            String s = String.valueOf(i);
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '2') ans++;
            }
        }
        return ans;
    }

    /**
     * 给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即左 子字符串和 右 子字符串）所能获得的最大得分。
     * 「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。
     */
    public int maxScore(String s) {
        int ans = 0;
        char[] chars = s.toCharArray();

        return ans;
    }

    public int[] exchange(int[] nums) {
        int[] ans = new int[nums.length];
        //输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
        int begin = 0;
        int end = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0 || nums[i] % 2 == 0) {
                ans[end] = nums[i];
                end--;
            } else {
                ans[begin] = nums[i];
                begin++;
            }
        }
        return ans;
    }

    public int arraySign(int[] nums) {
        int underNumber = 0;
        int zeroNumber = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) underNumber++;
            if (nums[i] == 0) zeroNumber++;
        }
        if (zeroNumber > 0) return 0;
        else if (underNumber % 2 == 0) return 1;
        else return -1;
    }

    public int[] sumZero(int n) {
        int[] ans = new int[n];
        int count = 0;
        for (int i = 1; i < ans.length; i++) {
            ans[i] = i;
            count += i;
        }
        ans[0] = -count;
        return ans;
    }

    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] words = sentence.split(" ");
        int index = -1;
        for (int i = 0; i < words.length; i++) {
            if (words[i].startsWith(searchWord)) {
                index = i + 1;
                break;
            }
        }
        return index;
    }

    public boolean canBeEqual(int[] target, int[] arr) {
        if (target.length != arr.length) return false;
        Arrays.sort(target);
        Arrays.sort(arr);
        for (int i = 0; i < target.length; i++) {
            if (target[i] != arr[i]) return false;
        }
        return true;
    }

    public int maxProductDemo(int[] nums) {
        int end = nums.length - 1;
        Arrays.sort(nums);
        return (nums[end] - 1) * (nums[end - 1] - 1);
    }

//    public static void main(String[] args) {
//
//        System.out.println(squareIsWhite("e7"));
//
//    }

    public static int[] shuffle(int[] nums, int n) {
        int[] ans = new int[nums.length];
        boolean flag = true;
        int index = 0;
        int next = n;
        for (int i = 0; i < ans.length; i++) {
            if (flag) {
                //拿到xn的值
                ans[i] = nums[index];
                index++;
                flag = false;
            } else {
                //拿到yn的值
                ans[i] = nums[next];
                next++;
                flag = true;
            }
        }
        return ans;
    }

    public static boolean squareIsWhite(String coordinates) {
        char chars = coordinates.charAt(0);
        char number = coordinates.charAt(1);
        //奇数是奇数黑  偶数是偶数黑
        if (chars % 2 == 0) {
            return number % 2 != 0;
        } else {
            return number % 2 == 0;
        }
    }

    /**
     * 判断一个字符串是否没有相同字符
     */
    public boolean isUnique(String astr) {
        List<Character> l = new ArrayList<>();
        char[] chars = astr.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (l.contains(chars[i])) {
                return false;
            } else {
                l.add(chars[i]);
            }
        }
        return true;
    }

    public int[] getConcatenation(int[] nums) {
        int[] ans = new int[nums.length * 2];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[i];
        }
        int index = 0;
        for (int i = nums.length - 1; i < ans.length && index < nums.length; i++) {
            ans[i] = nums[index];
            index++;
        }
        return ans;
    }

    public boolean canPartition(int[] nums) {
//        Arrays.sort(nums);
        int count = 0;
        for (int num : nums) {
            count += num;
        }
        return count % 2 == 0;
    }


    public static String reorderSpaces(String text) {
        List<String> list = new ArrayList<>();
        int zeroCount = 0;
        char[] chars = text.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') {
                zeroCount++;
                if (!stringBuilder.toString().equals("")) list.add(stringBuilder.toString());
                stringBuilder = new StringBuilder();
            } else {
                stringBuilder.append(chars[i]);
            }
        }
        if (zeroCount == 0) return text;
        if (!stringBuilder.toString().equals("")) list.add(stringBuilder.toString());
        if (list.size() == 1) {
            stringBuilder = new StringBuilder();
            stringBuilder.append(list.get(0));
            while (zeroCount > 0) {
                stringBuilder.append(" ");
                zeroCount--;
            }
            return stringBuilder.toString();
        }
        int split = zeroCount / (list.size() - 1);//间隔的0
        int end = zeroCount - (split * (list.size() - 1));//结尾的0
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            ans.append(list.get(i));
            for (int i1 = 0; i1 < split && i != list.size() - 1; i1++) {
                ans.append(" ");
            }
        }
        while (end > 0) {
            ans.append(" ");
            end--;
        }
        return ans.toString();
    }


    public int specialArray(int[] nums) {
        for (int i = 0; i <= nums.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] >= i) {
                    count++;
                }
            }
            if (count == i) {
                return i;
            }
        }
        return -1;
    }

    /*
    给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。 请你返回排序后的数组。
    //频率最小的一定是在最前面的  然后相同的按照降序依次往下进行遍历
     */
    public static int[] frequencySort(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> res = new HashMap<>();
        for (int num : nums) {
            list.add(num);
            res.put(num, res.getOrDefault(num, 0) + 1);
        }
        list.sort((a, b) -> {
            int aC = res.get(a);
            int bC = res.get(b);
            if (aC == bC) {
                return b - a;
            }
            return aC - bC;
        });
        int[] arr = new int[2];

        return list.stream().mapToInt(Integer::intValue).toArray();

    }

    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        char[] one = s1.toCharArray();
        char[] two = s2.toCharArray();
        Arrays.sort(one);
        Arrays.sort(two);
        for (int i = 0; i < one.length; i++) {
            if (one[i] != two[i]) return false;
        }
        return true;
    }

    public boolean isFlipedString(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        return (s2 + s2).contains(s1);
    }


    public static boolean isFlipedString2(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }

//
//    public static void main(String[] args) {
//        System.out.println(reformatNumber2("1-23-45 6"));
//    }

    public static String reformatNumber(String number) {
        number = number.replaceAll("-", "").replaceAll(" ", "");
        char[] chars = number.toCharArray();
        int n = chars.length;
        StringBuilder stringBuilder = new StringBuilder();
        a:
        for (int i = 0; i < n; i++) {
            stringBuilder.append(chars[i]);
            if (i % 3 == 0 && i != 0) stringBuilder.append("-");
            if (n - i - 1 <= 4) {
                switch (n - i - 1) {
                    case 4:
                        stringBuilder.append(chars[chars.length - 4])
                                .append(chars[chars.length - 3])
                                .append("-").append(chars[chars.length - 2]).
                                append(chars[chars.length - 1]);
                        break a;
                    case 3:
                        stringBuilder.append(chars[chars.length - 3]).append(chars[chars.length - 2]).append(chars[chars.length - 1]);
                        break a;
                    case 2:
                        stringBuilder.append(chars[chars.length - 2]).append(chars[chars.length - 1]);
                        break a;
                }
            }
        }
        return stringBuilder.toString();
    }

    public static String reformatNumber2(String number) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < number.length(); i++) {
            if (Character.isDigit(number.charAt(i))) {
                sb.append(number.charAt(i));
            }
        }
        int n = sb.length();
        StringBuilder ans = new StringBuilder();
        while (n > 4) {
            ans.append(sb.substring(0, 3)).append("-");
            sb.delete(0, 3);
            n -= 3;
        }
        if (n <= 3) ans.append(sb.toString());
        else ans.append(sb.substring(0, 2)).append("-").append(sb.substring(2, 4));
        return ans.toString();
    }

//    public static void main(String[] args) {
//        System.out.println(countGoodSubstrings(("aababcabc")));
//    }

    /**
     * 如果一个字符串不含有任何重复字符，我们称这个字符串为 好字符串。
     * 给你一个字符串 s，请你返回 s中长度为 3的 好子字符串 的数量。
     * 注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。
     * 子字符串 是一个字符串中连续的字符序列。
     */
    public static int countGoodSubstrings(String s) {
        int ans = 0;
        char[] chars = s.toCharArray();
        //abcde
        List<String> list = new ArrayList<>();
        StringBuilder builder;
        for (int i = 0; i < chars.length - 2; i++) {
            //截取到倒数第二个字符
            builder = new StringBuilder();
            char one = chars[i];
            char two = chars[i + 1];
            char three = chars[i + 2];
            if (one == three || two == one || three == two) continue;
            builder.append(one).append(two).append(three);
            String temp = builder.toString();
            list.add(temp);
        }
        return list.size();
    }

    //给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。
    //A 97  Z 122
    public int titleToNumber(String columnTitle) {
        int ans = 0;
        char[] chars = columnTitle.toCharArray();
        for (char aChar : chars) {
            int res = aChar - 'A' + 1;
            ans = ans * 26 + res;
        }
        return ans;
    }

    public boolean areAlmostEqual(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        char[] a = s1.toCharArray();
        char[] b = s2.toCharArray();
        char[] c = s1.toCharArray();
        char[] d = s2.toCharArray();
        Arrays.sort(c);
        Arrays.sort(d);
        for (int i = 0; i < a.length; i++) {
            if (c[i] != d[i]) return false;
        }
        int ans = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) ans++;
        }
        return ans < 2 || ans == 2;
    }


//    public static void main(String[] args) {
//        for (int i : plusOne2(new int[]{8, 9, 9, 9})) {
//            System.out.println(i);
//        }
//    }

    public static int[] plusOne(int[] digits) {
        StringBuilder b = new StringBuilder();
        for (int i = 0; i < digits.length; i++) {
            b.append(digits[i]);
        }
        BigInteger number = new BigInteger(b.toString());
        number = number.add(new BigInteger("1"));
        String temp = number.toString();
        int[] ans = new int[temp.length()];
        for (int i = 0; i < ans.length; i++) {
            char a = temp.charAt(i);
            ans[i] = Integer.parseInt(String.valueOf(a));
        }
        return ans;
    }

    public static int[] plusOne2(int[] digits) {
        boolean flag = false;
        if (digits.length == 1) {
            if (digits[0] < 9) {
                digits[0] += 1;
                return digits;
            } else {
                int[] result = new int[digits.length + 1];
                result[0] = 1;
                return result;
            }
        }
        int end = digits[digits.length - 1];
        if (end < 9) {
            digits[digits.length - 1] = end + 1;
            return digits;
        }
        digits[digits.length - 1] = 0;
        //到这里说明为9
        for (int i = digits.length - 2; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i] += 1;
                return digits;
            } else {
                //说明为9
                digits[i] = 0;
                flag = true;
            }
        }
        if (flag) {
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            return result;
        }
        return digits;
    }

    //暴力跑法
    public int[] twoSum1(int[] nums, int target) {
        //直接双循环匹配不解释
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }
        return new int[0];
    }

    //哈希表匹配
    public int[] twoSum2(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //创建哈希表用来存储键值对
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            //用目标值减去当前的值,然后去hashmap中寻找这个值的下标
            int number = target - nums[i];
            Integer numberIndex = hashMap.get(number);
            if (null != numberIndex) {
                //说明能找到，那我们给结果数组赋值并且返回结束当前循环
                result[0] = i;
                result[1] = numberIndex;
                break;
            } else {
                //没找到就将当前的值加入hashmap,key为值,value为值的下标
                hashMap.put(nums[i], i);
            }
        }
        return result;
    }


    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        for (String s : word1) {
            s1.append(s);
        }
        for (String s : word2) {
            s2.append(s);
        }
        return s1.toString().equals(s2.toString());
    }

//    public static void main(String[] args) {
//        System.out.println(interpret("(al)G(al)()()G"));
//
//    }


    /**
     * 请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成
     * Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ，"(al)" 解释为字符串 "al" 。
     * 然后，按原顺序将经解释得到的字符串连接成一个字符串。
     * 给你字符串 command ，返回 Goal 解析器 对 command 的解释结果
     */
    public static String interpret(String command) {
//        Map<String, String> map = new HashMap<>();
//        map.put("G", "G");
//        map.put("(al)", "al");
//        map.put("()", "o");
        return command.replace("(al)", "al").
                replace("()", "o");
    }


    /**
     * 给你一个由不同字符组成的字符串allowed和一个字符串数组words。
     * 如果一个字符串的每一个字符都在 allowed中，就称这个字符串是 一致字符串 。
     * 请你返回words数组中一致字符串 的数目。
     */
    public static int countConsistentStrings(String allowed, String[] words) {
        int ans = 0;
        char[] chars = allowed.toCharArray();
        for (String word : words) {
            if (word.equals(allowed)) ans++;//字符串相同
        }
        return ans;
    }

    public static int secondHighest(String s) {
        //去重
        List<Character> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        for (char aChar : chars) {
            if (!list.contains(aChar) && aChar <= '9') {
                list.add(aChar);
            }
        }
        int size = list.size();
        if (size > 1) {
            int res = list.get(size - 2) - '0';
            return res;
        }
        return -1;
    }

    public int passThePillow(int n, int time) {
        int t = time / n;//最少轮回次数
        int y = time % n;//剩余传递次数
        if (t % 2 == 0) return y + 1;//如果轮回次数为偶数则为正向 则我们返回的是正向传递剩余次数的下标指向
        else return n - y - 1;//反之我们需要从后面往前面递减

    }

    public static int passThePillow2(int n, int time) {
        int index = 1;
        boolean back = false;
        while (time-- > 0) {
            if (back) {
                index--;
            } else index++;
            if (index == n) {
                back = true;
            } else if (index == 0) back = false;
        }
        return index;
    }

    /*
    restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]

    其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false，
    如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆，为 false 则意味着可以包括任何餐馆。
    此外，我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器，它们分别考虑餐厅的价格因素和距离因素的最大值。
     */
    public static List<Integer> filterRestaurants(int[][] restaurants,
                                                  int veganFriendly,
                                                  int maxPrice,
                                                  int maxDistance) {
        List<Integer> ans = new ArrayList<>();
        List<List<Integer>> temp = new ArrayList<>();

        for (int i = 0; i < restaurants.length; i++) {
            if (restaurants[i][2] == veganFriendly || veganFriendly == 0) {
                //符合条件加入集合
                if (restaurants[i][3] <= maxPrice &&
                        restaurants[i][4] <= maxDistance) {
                    List<Integer> ad = new ArrayList<>();
                    for (int j = 0; j < restaurants[i].length; j++) {
                        ad.add(restaurants[i][j]);
                    }
                    temp.add(ad);
                }
            }
        }
        List<List<Integer>> collect = temp.stream().sorted((o1, o2) -> {
            return o2.get(1).equals(o1.get(1)) ? o2.get(0) - o1.get(0) : o2.get(1) - o1.get(1);
        }).collect(Collectors.toList());

        for (List<Integer> list : collect) {
            ans.add(list.get(0));
        }

        return ans;
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        //简单来说就是用一个一样的字符作为key 然后如果哈希表中不存在这个值就存进去
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);//排序后的字符 作为key
            String key = new String(chars);
            //如果哈希表中不存在这个异位词就加进去
            if (map.containsKey(key)) {
                map.get(key).add(str);
            } else {
                ArrayList<String> list = new ArrayList<>();
                list.add(str);
                map.put(key, list);
            }
        }
        return new ArrayList<>(map.values());

    }


    public static void main(String[] args) {
//        System.out.println(numDifferentIntegers("xtimt5kqkz9osexe56ezwwninlyeeqsq5m99904os3ygs12t31n1et4uwzmt5kvv6teisobuxt10k33v1aaxysg4y8nsivxdp3fo9dr7x58m8uc4ofm41ai77u8cvzr5r3s97f5otns59ubqk57xwl00xsp9w2oodt6yxcbscloyr9c2su8gca1ly6rrjufm25luhxhesxwn7bk1as9na4cbabxk"));
//        System.out.println(passThePillow2(3, 4));
//        int[][] res = {{1, 4, 1, 40, 10}, {2, 8, 0, 50, 5}, {3, 8, 1, 30, 4}, {4, 10, 0, 10, 3}, {5, 1, 1, 15, 1}};
//        int[][] res2 = {{1, 4, 1, 40, 10}, {2, 8, 0, 50, 5}, {3, 8, 1, 30, 4}, {4, 10, 0, 10, 3}, {5, 1, 1, 15, 1}};
//        List<Integer> list = filterRestaurants(res, 0, 50, 10);
//        for (Integer i : list) {
//            System.out.println(i);
//        }
    }

    public long findTheArrayConcVal(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        long ans = 0L;
        while (left <= right) {
            //得到当前串联值
            if (left == right) ans += nums[left];
            else {
                int lv = nums[left];
                int rv = nums[right];
                String str = lv + "" + rv;
                ans += Long.parseLong(str);
                left++;
                right--;
            }
        }
        return ans;
    }


    public static int numDifferentIntegers(String word) {
        Set<String> set = new HashSet<String>();
        int n = word.length(), p1 = 0, p2;
        while (true) {
            while (p1 < n && !Character.isDigit(word.charAt(p1))) {
                p1++;
            }
            if (p1 == n) {
                break;
            }
            p2 = p1;
            while (p2 < n && Character.isDigit(word.charAt(p2))) {
                p2++;
            }
            while (p2 - p1 > 1 && word.charAt(p1) == '0') { // 去除前导 0
                p1++;
            }
            set.add(word.substring(p1, p2));
            p1 = p2;
        }
        return set.size();
    }
}

/**
 * 分别======================================================================
 */
class MyCalendar {

    List<int[]> list;

    public MyCalendar() {
        list = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int i = 0; i < list.size(); i++) {
            int[] a = list.get(i);
            if (!(end - 1 < a[0] || start > a[1])) {
                return false;
            }
        }
        list.add(new int[]{start, end - 1});
        return true;
    }
}

/**
 * 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。
 * 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
 */
class MagicDictionary {
    private final List<String> list;

    public MagicDictionary() {
        list = new ArrayList<>();
    }

    public void buildDict(String[] dictionary) {
        list.addAll(Arrays.asList(dictionary));
    }

    public boolean search(String searchWord) {
        for (int i = 0; i < list.size(); i++) {
            String word = list.get(i);
            //首尾两个指针
            if (searchWord.length() == word.length()) {
                int first = 0;
                int count = 0;
                int end = searchWord.length() - 1;
                while (first <= end) {
                    if (count > 1) return false;
                    if (searchWord.charAt(first) == word.charAt(first)
                            && searchWord.charAt(end) == word.charAt(end)) {
                        //说明两个字母目前首尾相同
                        first++;
                        end--;
                    } else if (searchWord.charAt(first) != word.charAt(first)
                            && searchWord.charAt(end) != word.charAt(end) && first != end) {
                        break;
                    } else {
                        count++;
                        first++;
                        end--;
                    }
                }
                if (count == 1) return true;
            }
        }

        return false;
    }


}

class OrderedStream {
    private final String[] strings;
    int ptr;

    public OrderedStream(int n) {
        strings = new String[n + 1];
        ptr = 1;
    }

    public List<String> insert(int idKey, String value) {
        strings[idKey] = value;
        List<String> res = new ArrayList<>();
        while (ptr < strings.length && strings[ptr] != null) {
            res.add(strings[ptr++]);
        }
        return res;
    }
}
